1. Field of the Invention
This invention relates to caching of write requests and more particularly relates to regulating the number of write requests in a fixed-size cache.
2. Description of the Related Art
Nearly all computer software applications store information. Software applications store information on a volatile or non-volatile storage volume such as a hard disk, tape drive, solid state memory device, or other storage device. In some computer systems, the storage volume is part of the same machine on which the software application is executing. In other computer systems the storage volume is physically separated from the application. In these systems, a bus or network connects the software application and storage volume and enables communication between the software application and the storage volume.
Often, when the storage volume is physically separated from the application, multiple applications have access to a single storage volume and may try to write information to the storage volume at the same time. As a result, an application may try to write information to a storage volume while the storage volume is busy accommodating a write request from another application. Consequently, storage volumes can not always execute write requests immediately after receiving them.
A conventional approach to this problem is to store write requests in a cache until the storage volume can execute the write requests. Typically, the cache stores write requests in the order they are received. Write requests are taken from the cache, typically in the order they were received, and executed as the storage volume becomes available. Conventionally, the cache is physically located on the same machine as the application.
Caching write requests is effective as long as there is room in the cache for write requests. However, conventional caches are typically of a fixed size, these fixed-size caches can fill up with write requests during particularly busy periods of time. Once the write request cache fills up, additional write requests cannot be accepted from applications. Consequently, applications need to wait until the cache has free space and then re-submit write requests.
FIG. 1A is a chart illustrating the contents of an example cache 100. The example cache 100 has ten write request slots 102. Each slot 102 can store one write request. Of course, actual caches typically store hundreds, thousands, or more entries. The example cache 100 illustrated has ten write request slots 102 for simplicity.
Each write request can include information such as the name of the application making the request, the storage volume on which information is to be stored, a pointer to the data to be written or the data itself, and the like. The example cache 100 illustrates the name 104 of the application making the write request and the storage volume 106 on which information is to be written.
The example cache 100 contains three write requests 108,110,112. “Application A” submitted all three write requests 108,110,112. In this example, “Application A” is an application that records critical temperature data every 100 milliseconds. In this example, the operators of the storage volume have a service level agreement with the operators of “Application A” specifying that the storage volume operator will ensure that all write requests issued by “Application A” will be written on the storage volume without requiring “Application A” to wait, commonly referred to as blocking.
The example cache 100 stores write requests in their order of arrival with the oldest write request at bottom of the cache and the most recent write request at the top of the cache. The first write request 108 made by “Application A” is the next write request to be executed. The second write request 110 made by “Application A” will be executed after the first write request 108. Likewise, the third write request 112 will be executed after the second write request 110 has been executed.
FIG. 1B is a chart illustrating the contents of an example write request cache 130 accommodating write requests from two applications. “Application A” sends periodic write requests to record temperature data every 100 milliseconds. In contrast, “Application B” sends bursts of write requests at irregular intervals. In this example, the cache 130 has room for both “Application A” write requests 132 and a small burst of “Application B” write requests 134.
FIG. 1C is a chart illustrating the contents of an example write request cache 160. In this example cache 160, all available write request slots 102 have been filled by periodic “Application A” write requests 132 and two bursts 162,164 of “Application B” write requests. Consequently, the cache is full and there is no room for a subsequent critical “Application A” write request. Consequently, the next “Application A” write request may be dropped or delayed, resulting in a violation of the service level agreement between the operators of “Application A” and the operators of the service volume.
Some conventional systems reduce the likelihood of this overflow problem by implementing write request pacing. Write request pacing slows the rate of write requests entering the cache by forcing applications to delay write requests. However, conventional methods of pacing are very restrictive because they lack granularity. Conventional pacing methods assign the same pacing value to all write requests. Conventional methods of pacing slow the rate of all write requests in the cache and are unable to distinguish between high priority write requests and low priority write requests. In addition, conventional methods of pacing are unable to distinguish the write requests in the cache by their destination storage volume. Instead, when pacing is enabled all write requests in the cache are treated in the same manner.
From the foregoing discussion, it should be apparent that a need exists for an apparatus, system, and method for regulating the number of write requests in a fixed-size cache. The apparatus, system, and method should ensure that there is room in the cache for critical write requests by delaying non-critical write requests. Additionally, the apparatus, system, and method should provide a way to pace write requests based on their priority and their destination storage volume.